题目分析
第一眼看上去,直接brute暴力搜索,结果直接通过了,然后好奇心驱使我看了一下其他解法,竟然有更加巧妙的方法。小伙伴们能想得到吗?
二分查找
暴力法在这里我就不叙述了,一个一个比较,相等返回索引,最后返回-1即可。
为什么我一开始想不到二分查找呢?主要是因为一般我们认为要查找的是有序的序列。但是这里存在着一些空串,因此序列并不是有序的。
看了方法之后,我了解到,虽然空串导致序列并不是有序的,但是我们可以忽略空串,当mid所在的字符串为空时,我们可以顺序向下搜索第一个不是空串的位置,用这个位置进行比较。
当仅有words[0]不为空,这时需要遍历所有的情况,因此最坏的情况下算法的**时间复杂度仍是$O(n)$**。
1 | #include<iostream> |
刷题总结
这个题目给我的启发是非常大的,只要数据满足满足除了某些特定元素之外,其他都是有序的,那么我们也可以使用二分进行查找,在大部分数据下时间复杂度都会大大降低。